package com.example.javaproject.datastructure.test;

import java.util.LinkedList;
import java.util.Stack;

/**
 * Description: 利用2个队列实现一个堆栈,队列的实现利用LinkedList来做到
 * <p>实现的原理
 * <p>
 * <p>有队列Q1、Q2,添加元素的时候全部添加到Q1中如添加顺序为 1、2、3、4、5
 * <p>如果想要取出顺序为5，4，3，2，1 那么实现方案为
 * <p>
 * 取出的时候如果Q1有值Q2为空，将Q1队列只留最后一个队尾元素，其他装入Q2中，返回q1的最后一个元素 就是 5；
 * <p>
 * <p>继续
 * 取元素这个时候Q1为空Q2有值，将Q2队列只留最后一个队尾元素，其他装入Q1中，返回q2的最后一个元素 就是 4；
 * 如果循环达到栈结构的目的
 *
 * @see <a href="https://blog.csdn.net/u011328417/article/details/79436120">实现原理</a>
 * <br>Author：tian
 * <br>Time: 2019/3/12 13:54
 */
public class TwoQueueToStack {
    private LinkedList<Integer> q1 = new LinkedList<>();
    private LinkedList<Integer> q2 = new LinkedList<>();
    private int stackSize;

    public int getSize() {
        return stackSize;
    }

    public void push(int value) {
        q1.addLast(value);
        stackSize++;
    }

    public int pop() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return -1;
        }

        //Q1队列有数据
        if (q2.isEmpty()) {
            while (q1.size() > 1) {
                q2.addLast(q1.poll());
            }
            return q1.pop();
        }

        //Q2队列有数据
        if (q1.isEmpty()) {
            while (q2.size() > 1) {
                q1.addLast(q2.poll());
            }
            return q2.pop();
        }
        return -1;
    }

    public static void main(String[] args) {
        TwoQueueToStack twoQueueToStack = new TwoQueueToStack();
        twoQueueToStack.push(2);
        twoQueueToStack.push(3);
        twoQueueToStack.push(4);
        twoQueueToStack.push(5);
        twoQueueToStack.push(6);

        for (int i = 0; i < twoQueueToStack.stackSize; i++) {
            System.out.println(twoQueueToStack.pop());
        }
    }
}
